package com.lx.algorithm.Tree;

import java.io.Serializable;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * Description: 树的序列化跟反序列化
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-10-16 17:01:05
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-10-16     张李鑫                     1.0         1.0 Version
 */
public class TreeSerializable  {
    static class Node<T> {
        T value;
        Node left;
        Node right;

        public Node(T value) {
            this.value = value;
        }
    }

    /**
     * <p>
     * 先序序列化递归
     * </p>
     *
     * @param
     * @return void
     * @Author zlx
     * @date 2021/10/16
     */
    public static void preSerializable(Node node, Queue<String> queue) {
        if (null == node) {
            queue.add("#");
        } else {
            queue.add(String.valueOf(node.value));
            preSerializable(node.left, queue);
            preSerializable(node.right, queue);
        }
    }

    public static Node pre(Queue<String> queue) {
        String poll = queue.poll();
        if (null == poll) {
            return null;
        }
        Node<String> head = new Node<>(poll);
        head.left = pre(queue);
        head.right = pre(queue);
        return head;
    }


    public static void levelSerializable(Node node) {
        if (null == node) {
            return;
        }
        Stack<Node> nodes = new Stack<>();
        Queue<String> printStack = new LinkedList<>();

        nodes.push(node);
        while (!nodes.isEmpty()) {
            Node pop = nodes.pop();
            printStack.add(pop==null?"#":String.valueOf(pop.value));

            if (pop.right != null) {
                nodes.push(pop.right);
            }

            if (pop.left != null) {
                nodes.push(pop.left);
            }
        }
        printStack.forEach(System.out::println);

    }

    public static void main(String[] args) {
        Node<String> a = new Node<>("a");
        Node<String> b = new Node<>(null);
        Node<String> c = new Node<>("c");
        Node<String> d = new Node<>(null);
        Node<String> e = new Node<>("e");
        Node<String> f = new Node<>(null);
        Node<String> g = new Node<>("g");

        a.left = b;
        a.right = c;
        c.left = f;
        c.right = g;

        levelSerializable(a);

    }
}